/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next)
		return NULL;
	struct ListNode* p1 = head;
	struct ListNode* p2 = head->next;
	struct ListNode* prev = head;
	//判断是否带环
	while (p1 != p2) {
		if (!p2 || !p2->next)
			return NULL;
		prev = p1;
		p1 = p1->next;
		p2 = p2->next->next;
	}
	//走出while循环说明该链表带环，相遇点为p1/p2，在环内
	if (p1->next == p1)//特殊情况：链表带环，带环内只有一个节点，即该链表的最后一个节点的next是其本身。
		return p1;
        //(即当相遇点为入环点时，断开后两链表必然不相交，此处测试用例不全，只包括了一种情况：环内有一个节点)
	prev->next = NULL;
	//prev是p2/p1(相遇点)的上一个节点,在此处将环断开，形成两条链表，第一条由head到prev，第二条由p1/p2到prev
	//转换为链表相交问题)
	struct ListNode* cur1 = head;
	struct ListNode* cur2 = p1;
	while (cur2 != cur1) {
		cur1 = cur1 == NULL ? p1 : cur1->next;
		cur2 = cur2 == NULL ? head : cur2->next;
	}
	return cur1;//交点即为入口点
    }
};